package linearList;

import java.util.Iterator;
import java.util.LinkedList;

public class LinkList<T> implements Iterable<T>{
    private int N;
    private Node head;
    public LinkList(){
        this.N=0;
        this.head=new Node(null,null);
    }

    //空置线性表
    public void clear(){
        this.N = 0;
        this.head = new Node(null,null);
    }
    //判断线性表是否为空
    public boolean isEmpty(){
        return N==0;
    }
    public int length(){
        return N;
    }
    //向链表中插入一个元素
    public void insert(T t){
        Node newNode = new Node(t, null);
        Node n = head;
        while (n.next != null){
            n =n.next;
        }
        n.next = newNode;
        N++;
    }
    //向指定位置之前插入一个元素
    public void insert(int i , T t){
        if (i < 0 || i >= N){
            throw new RuntimeException("插入位置越界或者当前链表为空");
        }

        Node pre = head;
        for (int index = 0 ;index <= i-1 ; index++){
            pre = pre.next;
        }
        Node currNode = pre.next;
        Node newNOde = new Node(t, currNode);
        pre.next = newNOde;
        N++;
    }
    //删除并且返回第i个元素
    public Node remove(int i ){
        if (i<0 || i >= N){
            throw new RuntimeException("插入位置越界或者当前链表为空");
        }
        N--;
        Node pre = head.next;
        for (int index = 0 ; index < i-1; index++){
            pre = pre.next;
        }
        Node currNode = pre.next;
        Node lastNode  = currNode.next;
        pre.next = lastNode;
        return currNode;

    }
    //获取在链表中第一次出现的位置，并且返回
    public int index(T t){
        if (t == null || N==0){
            return -1;
        }
        Node tem = head;
        int i = 0;
        while (tem.next != null){
            tem = tem.next;
            if (tem.item.equals(t)){
                break;
            }
            i++;
        }
        return i;
    }

    public T get(int i ){
        if (i<0 || i >= N){
            throw new RuntimeException("插入位置越界或者当前链表为空");
        }
        Node n = head;
        for (int index  = 0; index < i; index++){
            n = n.next;
        }
        return n.item;
    }

    @Override
    public Iterator<T> iterator() {
        return new ItImp();
    }
    public class ItImp implements Iterator{
        private Node n;

        public ItImp( ) {
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }
    public void reverse(){
        if (N==0){
            return;
        }
        reverse(head.next);
    }
    public Node reverse(Node curr){
        if (curr.next == null){
            head.next = curr;
            return curr;
        }
        Node pre = reverse(curr.next);
        pre.next = curr;
        curr.next =null;
        return curr;
    }
    private class Node{
        T item;
        Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
    public int indexOf(T t) {
        Node n = head;
        for (int i = 0; n.next != null; i++) {
            n = n.next;
            if (n.item.equals(t)) {
                return i;
            }
        }
        return -1;
    }
    }
